package offer;

import java.util.ArrayList;
import java.util.List;

public class offer33 {
//    List<Integer> res = new ArrayList<>();
    public  static boolean verifyPostorder(int[] postorder) {
     int right = postorder.length-1;
     int left = 0;
      boolean res=  verify(postorder,left,right);
        return res;
    }

    private static boolean verify(int[] postorder, int left, int right) {
        if(left>=right) return true;
        int root= postorder[right];
        int i = left;
        int j = right;
        while (true)
        {
            while (postorder[j]>=root&&i<j)j--;
            while (postorder[i]<=root&&i<j)i++;
            break;
        }
//        for (int k = left; k <=i ; k++) {
//            if(postorder[k]>root) return false;
//        }
//        for (int k = i+1; k <=right; k++) {
//            if(postorder[k]<root) return false;
//        }
//        if(right-left<3) return true;
        boolean l = verify(postorder, left, i);
        boolean r = verify(postorder, i+1, right);

        return l&r&i==j;
    }

    public static void main(String[] args) {
        int []m = {1,3,2,6,5};
        boolean b = verifyPostorder(m);
        System.out.println(b);
    }
}
